In [ ]:
def test(test_name, method, exp_result, *argv):
if method(*argv) == exp_result:
print('{} - Success'.format(test_name))
else:
print('{} - Failed'.format(test_name))
In [ ]:
'''
Boggle
Memory: O(N^n)
Runtime: O(N^2)
'''
class Boggle:
#code assumes that both dimensions of grid are same
def __init__(self, grid, dictionary):
self.grid = grid
self.dictionary = dictionary
self.state = [[False for x in xrange(len(grid))] \
for y in xrange(len(grid))]
def find_all_nbrs(self, x, y):
nbrs = []
for i in xrange(max(0, x - 1), min(x + 2, len(self.grid))):
for j in xrange(max(0, y - 1), min(y + 2, len(self.grid))):
if i == x and j == y:
continue
if self.state[i][j] == False:
nbrs.append([i, j])
return nbrs
def find_words_rec(self, i, j, current, words):
if len(current) > 0 and (current in self.dictionary):
words.add(current)
# we can really speed up our algorithm if we have prefix method available
# for our dictionary by using code like below
#if not dictionary.is_prefix(current):
# // if current word is not prefix of any word in dictionary
# // we don't need to continue with search
# return
nbrs = self.find_all_nbrs(i, j)
for pr in nbrs:
first = pr[0]
second = pr[1]
current += self.grid[first][second]
self.state[first][second] = True
self.find_words_rec(first, second, current, words)
current = current[:-1] #equivalent to current = current[0:len(current) - 1]
self.state[first][second] = False
def find_all_words(self):
words = set([])
for i in xrange(0, len(self.grid)):
for j in xrange(0, len(self.grid)):
current_word = ""
self.find_words_rec(i, j, current_word, words)
return words
def main():
grid = [
['c', 'a', 't'],
['r', 'r', 'e'],
['t', 'o', 'n']
]
dictionary = set(["cat", "cater", "cartoon",
"toon", "moon", "not", "tone", "apple", "ton", "art"])
b = Boggle(grid, dictionary)
words = b.find_all_words()
for w in words:
print w,
main()
Given a phone number create a list of all the possible words that you can make given a dictionary from numbers to letters.
In python there is a itertools.permutations('abc') that would print all permutations given some input.
import itertools
itertools.permutations('abc')
[i for i in itertools.permutations('abc')]
# output permutations
In [3]:
letters_map = {'2':'ABC', '3':'DEF', '4':'GHI', '5':'JKL',
'6':'MNO', '7':'PQRS', '8':'TUV', '9':'WXYZ'}
def printWords(number, ):
#number is phone number
def printWordsUtil(numb, curr_digit, output, n):
if curr_digit == n:
print('%s ' % output)
return
for i in range(len(letters_map[numb[curr_digit]])):
output[curr_digit] = letters_map[number[curr_digit]][i]
printWordsUtil(numb, curr_digit+1, output, n)
if numb[curr_digit] == 0 or numb[curr_digit] == 1:
return
In [ ]:
def gen_phone(digits):
results = []
lookup = {
'0': ' ',
'1': ' ',
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
def decode_next(s, i):
if i == len(digits):
results.append(s)
return
for c in lookup[digits[i]]:
decode_next(s + c, i + 1)
decode_next('', 0)
return results
This is a good problem for working out variations where you count contiguous subsequence versus non continuous
The move with longest common subsequence is to start from the back of the strings and see if the letters are the same. Then increment with a dynamic programming approach where
In [ ]:
# Dynamic programming implementation of LCS problem
# Returns length of LCS for X[0..m-1], Y[0..n-1]
def lcs(X, Y, m, n):
L = [[0 for x in xrange(n+1)] for x in xrange(m+1)]
# Following steps build L[m+1][n+1] in bottom up fashion. Note
# that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]
for i in xrange(m+1):
for j in xrange(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
# Following code is used to print LCS
index = L[m][n]
# Create a character array to store the lcs string
lcs = [""] * (index+1)
lcs[index] = "\0"
# Start from the right-most-bottom-most corner and
# one by one store characters in lcs[]
i = m
j = n
while i > 0 and j > 0:
# If current character in X[] and Y are same, then
# current character is part of LCS
if X[i-1] == Y[j-1]:
lcs[index-1] = X[i-1]
i-=1
j-=1
index-=1
# If not same, then find the larger of two and
# go in the direction of larger value
elif L[i-1][j] > L[i][j-1]:
i-=1
else:
j-=1
print "LCS of " + X + " and " + Y + " is " + "".join(lcs)
# Driver program
X = "AGGTAB"
Y = "GXTXAYB"
m = len(X)
n = len(Y)
lcs(X, Y, m, n)
In [ ]:
passed in a list of dictionaries
also passed a character
passed single characted to int
if a character does not exist in the dict
then the defualt value it zero
find the highest possisble value for a character
in the dicts
now design it to take an abatrary operator and reutrn
the highest value based on the operator
and then have it return ascending and descending order
In [47]:
import time
import math
class TimeTravelDict:
def __init__(self):
self.dict = {}
def get(self, key, time):
if not self.dict[key]:
return -1
most_recent, value = math.inf, None
for a, b in self.dict[key]:
if b < time:
if (time - b) < most_recent:
most_recent = b
value = a
if value == None:
return -1
else:
return value
def put(self, key, value):
if not key in self.dict:
self.dict[key] = [(value, time.time())]
self.dict[key].append((value, time.time()))
print(self.dict[key])
tt = TimeTravelDict()
tt.put('a', 11)
tt.put('a', 12)
tt.put('a', 13)
tt.put('a', 14)
tt.get('a', 1513571590.2447577)
Out[47]:
Given a sorted dictionary of an alien language, find order of characters
Input: words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language "baa"
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.
Input: words[] = {"caa", "aaa", "aab"}
Output: Order of characters is 'c', 'a', 'b'
The idea is to create a graph of characters a then find topological sorting of the graph.
In [48]:
#[2::][1::2]
import collections
words = ["baa", "", "abcd", "abca", "cab", "cad"]
def alienOrder(words):
pre, suc = collections.defaultdict(set), collections.defaultdict(set)
for pair in zip(words, words[1:]):
print(pair)
for a, b in zip(*pair):
if a != b:
suc[a].add(b)
pre[b].add(a)
break
print('succ %s' % suc)
print('pred %s' % pre)
chars = set(''.join(words))
print('chars %s' % chars)
print(set(pre))
free = chars - set(pre)
print('free %s' % free)
order = ''
while free:
a = free.pop()
order += a
for b in suc[a]:
pre[b].discard(a)
if not pre[b]:
free.add(b)
if set(order) == chars:
return order
else:
False
# return order * (set(order) == chars)
alienOrder(words)
Out[48]:
In [ ]:
def binarySearch(alist, value):
mini = 0
maxi = len(alist)
while mini <= maxi:
print('here')
pivot = (maxi - mini) // 2
current_value = alist[pivot]
if current_value < value:
mini = pivot + 1
elif current_value > value:
maxi = pivot -1
else:
return pivot
return pivot or -1
test1 = [0, 5, 10 , 23, 46, 49, 78]
test2 = [0, 5, 10]
test3 = [0]
print(binarySearch(test1, 49))
print(binarySearch(test2, 10))
binarySearch(test3, 90)